/*
 * @Author: wwssaabb
 * @Date: 2021-12-15 16:01:39
 * @LastEditTime: 2021-12-15 17:29:15
 * @FilePath: \handwritten-code\排序算法\选择排序.js
 */


/* 
  选择排序, 时间复杂O(n2)
  主要思路:每一轮早到最小的值然后交换
*/

console.time(1)

function selectionSort(arr) {
  let len = arr.length,
    l = 0,
    r = 0,
    minIndex, temp
  while (l < len - 1) {
    while (r <= len - 1) {
      r++
      minIndex = Math.min(arr[minIndex], arr[r]) === arr[minIndex] ? minIndex : r
      if (r === len - 1) {
        temp = arr[l]
        arr[l] = arr[minIndex]
        arr[minIndex] = temp
        l++
        r = l
        minIndex = r
      }
    }
  }
  return arr
}

const arr = [89, 58, 66, 74, 15, 34, 99, 78, 45, 33, 21, 16, 85, 54]

//for的写法

function selectionSort(arr) {
  var len = arr.length;
  var minIndex, temp;
  for (var i = 0; i < len - 1; i++) {
    minIndex = i;
    for (var j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) { // 寻找最小的数
        minIndex = j; // 将最小数的索引保存
      }
    }
    temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}


console.log(selectionSort(arr))

console.timeEnd(1)